#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"../include/bst.h"

node *min_bst(node *head)
{
	node *temp;
	temp=head;
	while(temp->left != NULL)
		temp=temp->left;
	return temp;
}

node *max_bst(node *head)
{
	node *temp;
	temp=head;
	while(temp->right != NULL)
		temp=temp->right;
	return temp;
}

node *search_bst(node *head,char name[])
{
	node *temp;
	if(head==NULL || !strcmp(head->file_desc->filepath,name))
		return head;
	if(strcmp(head->file_desc->filepath,name) > 0)
		temp=search_bst(head->left,name);
	else 
		temp=search_bst(head->right,name);
	return temp;
}

void transplant(node *head,node *u,node *v)
{
	if(u->parent == NULL)
		head = v;
	else if(u == u->parent->left)
		u->parent->left = v;
	else
		u->parent->right = v;
	if(v != NULL)
		v->parent=u->parent;
}

node *create_bst(char name[])
{
	node *temp;
	int i=0;
	temp=(node *)malloc(sizeof(node));
	while(name[i] != '\0')
	{
		temp->file_desc->filepath[i]=name[i];	
		i++;
	}
	temp->file_desc->filepath[i]='\0';
	temp->left=NULL;
	temp->right=NULL;
	temp->parent=NULL;
	return temp;
}

node *insert_bst(node *head,char name[])
{
	node *temp,*p,*q;
	temp=NULL;
	p=head;
	q=create_bst(name);
	while(p != NULL)
	{
		temp=p;
		if(q->file_desc->filepath < p->file_desc->filepath)
			p=p->left;
		else
			p=p->right;
	}
	q->parent=temp;
	if(temp == NULL)
		head = q;
	else if(strcmp(q->file_desc->filepath,temp->file_desc->filepath) < 0)
		temp->left = q;
	else
		temp->right = q;
	return head;
	

}

node *delete_bst(node *head,char name[])
{
	node *temp,*min;
	temp = (node *)search_bst(head,name);
	if(temp->left == NULL)
		transplant(head,temp,temp->right);
	else if(temp->right == NULL)
		transplant(head,temp,temp->right);
	else
	{
		min=min_bst(temp->right);
		if(min->parent != temp)
		{
			transplant(head,min,min->right);
			min->right = temp->right;
			min->right->parent = min;
		}
		transplant(head,temp,min);
		min->left = temp->left;
		min->left->parent = min;
	}	
	return head;
}

void inorder(node *head)
{
	if(head == NULL);
	else
	{
		inorder(head->left);
		printf("%s\n",head->file_desc->filepath);
		inorder(head->right);
	}
}
